{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Unequal Adjacent Groups Subsequence I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getWordsInLongestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长相邻不相等子序列 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和一个下标从&nbsp;<strong>0</strong>&nbsp;开始的字符串数组&nbsp;<code>words</code>&nbsp;，和一个下标从 <strong>0</strong>&nbsp;开始的 <strong>二进制</strong>&nbsp;数组&nbsp;<code>groups</code>&nbsp;，两个数组长度都是&nbsp;<code>n</code>&nbsp;。</p>\n",
    "\n",
    "<p>你需要从下标&nbsp;<code>[0, 1, ..., n - 1]</code>&nbsp;中选出一个&nbsp;<strong>最长子序列</strong>&nbsp;，将这个子序列记作长度为 <code>k</code> 的&nbsp;<code>[i<sub>0</sub>, i<sub>1</sub>, ..., i<sub>k - 1</sub>]</code>&nbsp;，对于所有满足&nbsp;<code>0 &lt; j + 1 &lt; k</code>&nbsp;的&nbsp;<code>j</code>&nbsp;都有&nbsp;<code>groups[i<sub>j</sub>] != groups[i<sub>j + 1</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个字符串数组，它是下标子序列&nbsp;<strong>依次</strong>&nbsp;对应&nbsp;<code>words</code>&nbsp;数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。</p>\n",
    "\n",
    "<p><strong>子序列</strong>&nbsp;指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。</p>\n",
    "\n",
    "<p><b>注意：</b><code>words</code>&nbsp;中的字符串长度可能 <strong>不相等</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, words = [\"e\",\"a\",\"b\"], groups = [0,0,1]\n",
    "<b>输出：</b>[\"e\",\"b\"]\n",
    "<strong>解释：</strong>一个可行的子序列是 [0,2] ，因为 groups[0] != groups[2] 。\n",
    "所以一个可行的答案是 [words[0],words[2]] = [\"e\",\"b\"] 。\n",
    "另一个可行的子序列是 [1,2] ，因为 groups[1] != groups[2] 。\n",
    "得到答案为 [words[1],words[2]] = [\"a\",\"b\"] 。\n",
    "这也是一个可行的答案。\n",
    "符合题意的最长子序列的长度为 2 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, words = [\"a\",\"b\",\"c\",\"d\"], groups = [1,0,1,1]\n",
    "<b>输出：</b>[\"a\",\"b\",\"c\"]\n",
    "<b>解释：</b>一个可行的子序列为 [0,1,2] 因为 groups[0] != groups[1] 且 groups[1] != groups[2] 。\n",
    "所以一个可行的答案是 [words[0],words[1],words[2]] = [\"a\",\"b\",\"c\"] 。\n",
    "另一个可行的子序列为 [0,1,3] 因为 groups[0] != groups[1] 且 groups[1] != groups[3] 。\n",
    "得到答案为 [words[0],words[1],words[3]] = [\"a\",\"b\",\"d\"] 。\n",
    "这也是一个可行的答案。\n",
    "符合题意的最长子序列的长度为 3 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == words.length == groups.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 10</code></li>\n",
    "\t<li><code>0 &lt;= groups[i] &lt; 2</code></li>\n",
    "\t<li><code>words</code>&nbsp;中的字符串 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>words[i]</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-unequal-adjacent-groups-subsequence-i](https://leetcode.cn/problems/longest-unequal-adjacent-groups-subsequence-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-unequal-adjacent-groups-subsequence-i](https://leetcode.cn/problems/longest-unequal-adjacent-groups-subsequence-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[\"e\",\"a\",\"b\"]\\n[0,0,1]', '4\\n[\"a\",\"b\",\"c\",\"d\"]\\n[1,0,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        for i in range(n):\n",
    "            if groups[i] != pre:\n",
    "                ans.append(words[i])\n",
    "                pre = groups[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans_id = [0]\n",
    "        a = groups[0]\n",
    "        for i in range(1, n):\n",
    "            if groups[i] != a:\n",
    "                ans_id.append(i)\n",
    "                a = groups[i]\n",
    "        return [words[idi] for idi in ans_id]\n",
    "        # def check(mid):\n",
    "        #     a = groups[0]\n",
    "        #     v = 1\n",
    "        #     for i in range(1, n):\n",
    "        #         if groups[i] != a:\n",
    "        #             a = groups[i]\n",
    "        #             v += 1\n",
    "\n",
    "        #     return\n",
    "        \n",
    "        # left = 0\n",
    "        # right = n\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "        #     if check(mid):\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "        # return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(1, n):\n",
    "            if groups[i] != groups[i - 1]:\n",
    "                ans.append(words[i-1])\n",
    "        return ans + [words[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            if groups[i] == groups[i - 1]:\n",
    "                del groups[i]\n",
    "                del words[i]\n",
    "                i -= 1\n",
    "                n -= 1\n",
    "            i += 1\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        cur = -1\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if groups[i]!=cur:\n",
    "                cur = groups[i]\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def func(n,words,groups):\n",
    "            index =0 \n",
    "            index_list = [index]\n",
    "            result = []\n",
    "\n",
    "            for i in range(1,n):\n",
    "                if groups[i]!=groups[index]:\n",
    "                    index_list.append(i)\n",
    "                    index = i\n",
    "\n",
    "            for i in index_list:\n",
    "                result.append(words[i])\n",
    "\n",
    "            return result\n",
    "        \n",
    "        return func(n,words,groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, (x, y) in enumerate(pairwise(groups)):\n",
    "            if x != y:\n",
    "                ans.append(words[i])\n",
    "        ans.append(words[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        # 前i个 上个取了1 能够取得的最大长度\n",
    "        ans = [words[0]]\n",
    "        for i in range(1, n):\n",
    "            if groups[i] == groups[i-1]:\n",
    "                if len(words[i]) > len(ans[-1]):\n",
    "                    ans[-1] = words[i]\n",
    "            else: ans.append(words[i])\n",
    "        return ans\n",
    "                \n",
    "#         f = [[0,0,[]] for _ in range(n+1)]\n",
    "#         if groups[0] == 0:\n",
    "#             f[0][0] = -inf\n",
    "#         else: f[0][1] = -inf\n",
    "#         s = \"\"\n",
    "#         for i in range(n):\n",
    "#             f[i+1][1] = f[i][1]\n",
    "#             f[i+1][2] = f[i][2]\n",
    "#             if groups[i] == 1:\n",
    "#                 if f[i][0] + len(words[i]) > f[i][1]:\n",
    "#                     f[i+1][1] = f[i][0] + len(words[i])\n",
    "#                     f[i+1][2] = f[i][2] + [words[i]]\n",
    "#             f[i+1][0] = f[i][0]\n",
    "#             if groups[i] == 0:\n",
    "#                 if f[i][1] + len(words[i]) > f[i][0]:\n",
    "#                     f[i+1][0] = f[i][1] + len(words[i])\n",
    "#                     f[i+1][2] = f[i][2] + [words[i]]\n",
    "                    \n",
    "#         print(f)\n",
    "#         return f[n][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if i == 0 or groups[i] != groups[i - 1]:\n",
    "                res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        indexes = []\n",
    "        prev = ~groups[0]\n",
    "        for i, v in enumerate(groups):\n",
    "            if v != prev:\n",
    "                indexes.append(i)\n",
    "                prev = v\n",
    "        return [words[i] for i in indexes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        a=groups[0]\n",
    "        ans=[words[0]]\n",
    "        for i,v in enumerate(groups):\n",
    "            if v!=a:\n",
    "                a=v\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans=[words[0]]\n",
    "        flag=groups[0]\n",
    "        n=len(groups)\n",
    "        for i in range(n):\n",
    "            if groups[i]==1-flag:\n",
    "                ans+=[words[i]]\n",
    "                flag=1-flag\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        N = len(groups)\n",
    "        f = [ [ 0 ] * 2 for _ in range(N) ]\n",
    "        dp = [ [], [] ]\n",
    "        dp[groups[0]].append(words[0])\n",
    "        f[0][groups[0]] = 1\n",
    "        for j in range(1, N):\n",
    "            if f[j-1][1-groups[j]] + 1 > f[j-1][groups[j]]:\n",
    "                f[j][groups[j]] = f[j-1][1-groups[j]] + 1\n",
    "                dp[groups[j]] = dp[1-groups[j]] + words[j:j+1]\n",
    "            else:\n",
    "                f[j][groups[j]] = f[j-1][groups[j]]\n",
    "            f[j][1-groups[j]] = f[j-1][1-groups[j]]\n",
    "        # print(f, dp)\n",
    "        return dp[0] if f[N-1][0] > f[N-1][1] else dp[1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        cur = groups[0] ^ 1\n",
    "        for i, x in enumerate(groups):\n",
    "            if cur ^ x:\n",
    "                cur = x\n",
    "                res.append(words[i])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        before = 0\n",
    "        ans = [] \n",
    "        tmp = [] \n",
    "\n",
    "        for i in range(n):\n",
    "            before = groups[i]\n",
    "            tmp = [i]\n",
    "            for j in range(i+1, n):\n",
    "                if groups[j] != before:\n",
    "                    tmp.append(j)\n",
    "                    before = groups[j]\n",
    "            #print(tmp,ans)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp\n",
    "        \n",
    "        \n",
    "        result = [] * len(ans)\n",
    "        for i, c in enumerate(ans):\n",
    "            result.append(words[c])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        n = len(words)\n",
    "        flag = groups[0]\n",
    "        for i in range(n):\n",
    "            if groups[i] == flag:\n",
    "                res.append(words[i])\n",
    "                flag = 1 - flag\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        res = []\n",
    "        last = '0'\n",
    "        for i in range(n):\n",
    "            if groups[i]!=last:\n",
    "                res.append(words[i])\n",
    "                last = groups[i]\n",
    "        \n",
    "        res2 = []\n",
    "        last = '1'\n",
    "        for i in range(n):\n",
    "            if groups[i]!=last:\n",
    "                res2.append(words[i])\n",
    "                last = groups[i]\n",
    "        # print(res,res2)\n",
    "        return res if len(res)>len(res2) else res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        s=[0]\n",
    "        for i in range(1,len(groups)):\n",
    "            if groups[i]!=groups[s[-1]]:\n",
    "                s.append(i)\n",
    "        res=[0 for _ in range(0,len(s))]\n",
    "        for i in range(0,len(s)):\n",
    "            res[i]=words[s[i]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        if n == 0:\n",
    "            return res\n",
    "        now = groups[0]\n",
    "        res.append(words[0])\n",
    "\n",
    "        for i in range(n):\n",
    "            if groups[i] != now:\n",
    "                now = groups[i]\n",
    "                res.append(words[i])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(n) :\n",
    "            if i and groups[i] == groups[i - 1] :\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        for w, g in zip(words, groups):\n",
    "            if g!=pre:\n",
    "                ans.append(w)\n",
    "                pre = g\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        judge=100\n",
    "        index=[]\n",
    "        for i,x in enumerate(groups):\n",
    "            if x!=judge:\n",
    "                index.append(i)\n",
    "                judge=x\n",
    "        ans=[]\n",
    "        for i in index:\n",
    "            ans.append(words[i])\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        i = 1\n",
    "        while i < len(words):\n",
    "            if groups[i] == groups[i-1]:\n",
    "                del words[i]\n",
    "                del groups[i]\n",
    "                i -= 1\n",
    "            i += 1\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i == n - 1 or groups[i] != groups[i + 1]: ans.append(words[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        f = [0 for _ in range(n)]\n",
    "        fa = [-1 for _ in range(n)]\n",
    "        ans = ans_idx = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if groups[i] != groups[j]:\n",
    "                    if f[i] < f[j] + 1:\n",
    "                        f[i] = f[j] + 1\n",
    "                        fa[i] = j\n",
    "            if ans <= f[i]:\n",
    "                ans_idx = i\n",
    "        res = []\n",
    "        while ans_idx >= 0:\n",
    "            res.insert(0, words[ans_idx])\n",
    "            ans_idx = fa[ans_idx]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        last = -1\n",
    "        res = []\n",
    "        for i in range(len(groups)):\n",
    "            if groups[i]!=last:\n",
    "                res.append(words[i])\n",
    "            last = groups[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        loc = 0\n",
    "        while loc < n - 1:\n",
    "            if groups[loc] != groups[loc + 1]:\n",
    "                ans.append(words[loc])\n",
    "            loc +=1\n",
    "        ans.append(words[n - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        pre = -1\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if groups[i] != pre:\n",
    "                ans.append(words[i])\n",
    "                pre = groups[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        before = 0\n",
    "        ans = [] \n",
    "        tmp = [] \n",
    "\n",
    "        for i in range(n):\n",
    "            before = groups[i]\n",
    "            tmp = [i]\n",
    "            for j in range(i+1, n):\n",
    "                if groups[j] != before:\n",
    "                    tmp.append(j)\n",
    "                    before = groups[j]\n",
    "            #print(tmp,ans)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp\n",
    "        \n",
    "        \n",
    "        result = [] * len(ans)\n",
    "        for i, c in enumerate(ans):\n",
    "            result.append(words[c])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        clt, res = [], []\n",
    "        for i, group in enumerate(groups):\n",
    "            if len(clt) > 0 and clt[-1] == group:\n",
    "                continue\n",
    "            clt.append(group)\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i == n - 1 or groups[i] != groups[i + 1]: ans.append(words[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        if n == 1:\n",
    "            return words\n",
    "        res = []\n",
    "        res.append(words[0])\n",
    "        for i in range(1, n):\n",
    "            if groups[i] != groups[i - 1]:\n",
    "                res.append(words[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [c for c,(x,y) in zip(words,pairwise(groups)) if x!=y] + [words[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        len0, len1 = 0, 0\n",
    "        len0_idx, len1_idx = [], []\n",
    "        ans = 0\n",
    "        ans_idx = []\n",
    "        for i, bit in enumerate(groups):\n",
    "            if bit == 0:\n",
    "                if len1 + 1 > ans:\n",
    "                    len0_idx = len1_idx.copy()\n",
    "                    len0_idx.append(i)\n",
    "                    len0 = len1 + 1\n",
    "                    ans = len0\n",
    "                    ans_idx = len0_idx\n",
    "            elif bit == 1:\n",
    "                if len0 + 1 > ans:\n",
    "                    len1_idx = len0_idx.copy()\n",
    "                    len1_idx.append(i)\n",
    "                    len1 = len0 + 1\n",
    "                    ans = len1\n",
    "                    ans_idx = len1_idx\n",
    "        return list(map(lambda x: words[x], ans_idx))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        idx = 0\n",
    "        for g, it in groupby(groups):\n",
    "            if idx >= len(words): break\n",
    "            ans.append(words[idx])\n",
    "            idx += len(list(it))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        index=[]\n",
    "        index.append(0)\n",
    "        for i in range(1, len(groups)):\n",
    "            if groups[index[-1]]!=groups[i]:\n",
    "                index.append(i)\n",
    "\n",
    "        res = []\n",
    "        for i in index:\n",
    "            res.append(words[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans1,ans2 = [],[]\n",
    "        target = 1\n",
    "        for v,k in zip(words,groups):\n",
    "            if k == target:\n",
    "                ans1.append(v)\n",
    "                target= int(not target)\n",
    "        target = 0\n",
    "        for v,k in zip(words,groups):\n",
    "            if k == target:\n",
    "                ans2.append(v)\n",
    "                target=int(not target)\n",
    "        return ans1 if len(ans1) > len(ans2) else ans2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        cur = 1-groups[0]\n",
    "        for i in range(n):\n",
    "            if cur+groups[i]==1:\n",
    "                cur = 1-cur\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        for (i, j) in pairwise(groups):\n",
    "            print(\"%d %d\" %(i, j))\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        now = groups[0]\n",
    "        res = [words[0]]\n",
    "        for i in range(1,n):\n",
    "            if groups[i] != now:\n",
    "                res.append(words[i])\n",
    "                now = groups[i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        def back(i,cur):\n",
    "            if i>=n:\n",
    "                return cur \n",
    "            j = i+1\n",
    "            while j<n and groups[j]==groups[j-1]:\n",
    "                j+=1\n",
    "            if j<n:\n",
    "                cur.append(j)\n",
    "            return back(j,cur)\n",
    "        \n",
    "\n",
    "        f= back(0,[0])\n",
    "        ans = []\n",
    "        for i in f:\n",
    "            ans.append(words[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "\n",
    "        candi = None\n",
    "        for i in range(n-1):\n",
    "            if i == 0 or groups[i+1] != groups[i]:\n",
    "                if candi and n-i-1 < len(candi): continue\n",
    "                t = [i]\n",
    "                for j in range(i+1, n):\n",
    "                    if groups[j] != groups[t[-1]]:\n",
    "                        t.append(j)\n",
    "                if candi is None or len(t)-1 > len(candi):\n",
    "                    candi = t[1:] if i else t\n",
    "\n",
    "        ans = [words[t] for t in candi] if candi else [words[0]]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        expect = 0\n",
    "        res1 = []\n",
    "        for i in range(len(groups)):\n",
    "            if groups[i] == expect:\n",
    "                res1.append(words[i])\n",
    "                expect = 1 - expect\n",
    "        expect = 1\n",
    "        res2 = []\n",
    "        for i in range(len(groups)):\n",
    "            if groups[i] == expect:\n",
    "                res2.append(words[i])\n",
    "                expect = 1 - expect\n",
    "        return res1 if len(res1) >= len(res2) else res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        currentMaxLength = 0\n",
    "        answerIndexList = []\n",
    "        currentIndexList = []\n",
    "        currentGroupList = []\n",
    "        currentLength = 0\n",
    "        for i in range(n):\n",
    "            # try to add groups[i] into answerIndexList\n",
    "            if len(currentGroupList) == 0 or currentGroupList[-1] != groups[i]:\n",
    "                currentGroupList.append(groups[i])\n",
    "                currentIndexList.append(i)\n",
    "            else:\n",
    "                while len(currentGroupList)!=0 and currentGroupList[-1] == groups[i]:\n",
    "                    currentGroupList.pop(-1)\n",
    "                    currentIndexList.pop(-1)\n",
    "                currentGroupList.append(groups[i])\n",
    "                currentIndexList.append(i)\n",
    "            \n",
    "            # then we can process the length\n",
    "            currentLength = len(currentIndexList)\n",
    "            if currentLength > currentMaxLength:\n",
    "                currentMaxLength = currentLength\n",
    "                answerIndexList = copy.deepcopy(currentIndexList)\n",
    "                \n",
    "        return [words[index] for index in answerIndexList]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [words[i] for i, x in enumerate(groups) if i == 0 or x != groups[i - 1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ls0,ls1 = [[0,-1]],[[1,-1]]\n",
    "        for i in range(n):\n",
    "            c = groups[i]\n",
    "            if c != ls0[-1][1]:\n",
    "                ls0.append([i,c])\n",
    "            if c != ls1[-1][1]:\n",
    "                ls1.append([i,c])\n",
    "        \n",
    "        print(ls0,ls1)\n",
    "        ans = []\n",
    "        if len(ls0) > len(ls1):\n",
    "            ls0.pop(0)\n",
    "            for index,_ in ls0:\n",
    "                ans.append(words[index])\n",
    "        else:\n",
    "            ls1.pop(0)\n",
    "            for index,_ in ls1:\n",
    "                ans.append(words[index])\n",
    "\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "                \n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        # 定义f[i + 1] 表示以i为结尾的子序列所能取得的最大值\n",
    "        # j从0到i-1枚举\n",
    "        # 如果words[j]和words[i]的距离是1，且len(words[j]) == len(words[i]) 且groups[j] !=groups[i]\n",
    "        # 去长度最大值\n",
    "        def hdist1(a: str, b: str) -> int:\n",
    "            res = 0\n",
    "            for a1, b1 in zip(a, b):\n",
    "                if a1 != b1:\n",
    "                    res += 1\n",
    "                    if res > 1:\n",
    "                        return False\n",
    "            return res == 1\n",
    "        f = [[] for _ in range(n + 1)]\n",
    "        ans = []\n",
    "        for i, (w, g) in enumerate(zip(words, groups)):\n",
    "            f[i + 1].append(w)\n",
    "            for j in range(i):\n",
    "                if groups[j] != g:\n",
    "                    if len(f[j + 1]) + 1 > len(f[i + 1]):\n",
    "                        f[i + 1] = f[j + 1] + [w]\n",
    "            if len(f[i + 1]) > len(ans):\n",
    "                ans = f[i + 1]\n",
    "        return ans\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        maxlen = [0 for _ in range(n)]\n",
    "        wordss = [[] for _ in range(n)]\n",
    "        maxlen[0] = 1\n",
    "        wordss[0] = [words[0]]\n",
    "        for i in range(1, n):\n",
    "            cur = -1\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j] and maxlen[j] > maxlen[i]:\n",
    "                    maxlen[i] = maxlen[j]\n",
    "                    cur = j\n",
    "            if cur != -1:\n",
    "                wordss[i] = copy.deepcopy(wordss[cur])\n",
    "            maxlen[i] += 1\n",
    "            wordss[i].append(words[i])\n",
    "        maxx = 0\n",
    "        pos = 0\n",
    "        for i in range(n):\n",
    "            if maxlen[i] > maxx:\n",
    "                maxx = maxlen[i]\n",
    "                pos = i\n",
    "        return wordss[pos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        max_len = [[0,0] for _ in range(n)]\n",
    "        sol = [[[],[]] for _ in range(n)]\n",
    "        \n",
    "        max_len[0][0] = 0\n",
    "        max_len[0][1] = 1\n",
    "        sol[0][1] = [0]\n",
    "        \n",
    "        def satisfy(s1, s2):\n",
    "            if len(s1) != len(s2):\n",
    "                return False\n",
    "            diff = False\n",
    "            for a,b in zip(s1, s2):\n",
    "                if a != b:\n",
    "                    if not diff:\n",
    "                        diff = True\n",
    "                    else:\n",
    "                        return False\n",
    "            if not diff:\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        for s in range(1, n):\n",
    "            find = []\n",
    "            for further in range(s-1, -1, -1):\n",
    "                if groups[further] != groups[s]:\n",
    "                    find.append(further)\n",
    "            max_len[s][0], tag = max([max_len[s-1][0], 0], [max_len[s-1][1], 1])\n",
    "            if not tag:\n",
    "                sol[s][0] = sol[s-1][0]\n",
    "            else:\n",
    "                sol[s][0] = sol[s-1][1]\n",
    "\n",
    "            if not find:\n",
    "                max_len[s][1] = 1\n",
    "                sol[s][1] = [s]\n",
    "            else:\n",
    "                max_len[s][1], maxf = max([(max_len[f][1] + 1,f) for f in find])\n",
    "                sol[s][1] = sol[maxf][1] + [s]\n",
    "        \n",
    "        _, tag = max((max_len[n-1][0], 0), (max_len[n-1][1], 1))\n",
    "        if tag:\n",
    "            return [words[i] for i in sol[n-1][1]]\n",
    "        else:\n",
    "            return [words[i] for i in sol[n-1][0]]\n",
    "\n",
    "# print(Solution().getWordsInLongestSubsequence(3, [\"bab\",\"dab\",\"cab\"], [1,2,2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getWordsInLongestSubsequence(self, n, words, groups):\n",
    "\n",
    "        def get_dist(i, j):\n",
    "            return 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return []\n",
    "\n",
    "            ans = []\n",
    "            for j in range(i + 1, n):\n",
    "                if groups[i] == groups[j]:\n",
    "                    continue\n",
    "                if get_dist(i, j) != 1:\n",
    "                    continue\n",
    "                result = dfs(j)\n",
    "                ans = max(ans, result, key=lambda x: len(x))\n",
    "            return [i] + ans\n",
    "\n",
    "        indices = dfs(0)\n",
    "        results = []\n",
    "        for index in indices:\n",
    "            results += [words[index]]\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        \n",
    "        stat = [[False]*n for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, i):\n",
    "                if groups[i]!=groups[j]:\n",
    "                    stat[i][j] = True\n",
    "        \n",
    "        dp = [1]*n\n",
    "        indexs = [[0]]\n",
    "        res = 0\n",
    "        max_len = 1\n",
    "        for i in range(1, n):\n",
    "            tmp_index = -1\n",
    "            cnt = 0\n",
    "            for j in range(0, i):\n",
    "                if stat[i][j]:\n",
    "                    if dp[j] > cnt:\n",
    "                        cnt = dp[j]\n",
    "                        tmp_index = j\n",
    "            if tmp_index != -1:\n",
    "                indexs.append(indexs[tmp_index]+[i])\n",
    "                dp[i] = cnt+1\n",
    "            else:\n",
    "                indexs.append([i])\n",
    "            if len(indexs[-1])> max_len:\n",
    "                max_len = len(indexs[-1])\n",
    "                res = i\n",
    "        return [words[x] for x in indexs[res]]\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = [0]\n",
    "        def dfs(index):\n",
    "            for i in range(index+1,n):\n",
    "                if groups[i] != groups[index]:\n",
    "                    ans.append(i)\n",
    "                    dfs(i)\n",
    "                    return\n",
    "        dfs(0)\n",
    "        re = list(map(lambda x:words[x],ans))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        dp=[[i] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if groups[j]!=groups[i]:\n",
    "                    dp[j]=max(dp[j],dp[i]+[j],key=len)\n",
    "\n",
    "        arr=max(dp,key=len)\n",
    "        return [words[u] for i,u in enumerate(arr)]\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(\n",
    "        self, n: int, words: List[str], groups: List[int]\n",
    "    ) -> List[str]:\n",
    "        # dp[i] 表示以 words[i] 结尾的最长子序列长度\n",
    "        dp = [1] * n\n",
    "        pre = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        pre[i] = j\n",
    "\n",
    "        maxLen = max(dp)\n",
    "        maxIndex = dp.index(maxLen)\n",
    "        res = []\n",
    "        while maxIndex != -1:\n",
    "            res.append(words[maxIndex])\n",
    "            maxIndex = pre[maxIndex]\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')\n",
    "INFMAX = float('inf')\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "\n",
    "def input():\n",
    "    return sys.stdin.readline().rstrip()\n",
    "\n",
    "\n",
    "def end(r=-1):\n",
    "    print(r)\n",
    "    exit()\n",
    "\n",
    "\n",
    "# --idea\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/15 16:19\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str],\n",
    "                                     groups: List[int]) -> List[str]:\n",
    "        nums = [0]\n",
    "        for v in range(1, n):\n",
    "            if groups[v] != groups[nums[-1]]:\n",
    "                nums.append(v)\n",
    "        return [words[i] for i in nums]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        pref = list(range(n))\n",
    "        def ham(s, t):\n",
    "            if len(s) != len(t):\n",
    "                return False\n",
    "            dis = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] != t[i]:\n",
    "                    dis += 1\n",
    "            return dis == 1\n",
    "    \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            r = 1\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j]:\n",
    "                    if 1 + dfs(j) > r:\n",
    "                        pref[i] = j\n",
    "                        r = 1 + dfs(j)\n",
    "            return r\n",
    "        \n",
    "        m = 1\n",
    "        mi = 0\n",
    "        for i in range(n):\n",
    "            k = dfs(i)\n",
    "            if m < k:\n",
    "                m = k\n",
    "                mi = i\n",
    "        l = []\n",
    "        while pref[mi] != mi:\n",
    "            l.append(words[mi])\n",
    "            mi = pref[mi]\n",
    "        l.append(words[mi])\n",
    "        l.reverse()\n",
    "        dfs.cache_clear()\n",
    "        return l\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, w: List[str], g: List[int]) -> List[str]:\n",
    "        \n",
    "        def f(i, pre, path):\n",
    "            if i == n: return\n",
    "            if g[i] == pre:\n",
    "                f(i + 1, pre, path)\n",
    "                return\n",
    "            path.append(w[i])\n",
    "            f(i + 1, g[i], path)\n",
    "        \n",
    "        ans1, ans2 = [], []\n",
    "        \n",
    "        f(0, 0, ans1)\n",
    "        f(0, 1, ans2)\n",
    "        \n",
    "        if len(ans1) >= len(ans2):\n",
    "            return ans1\n",
    "        else:\n",
    "            return ans2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')\n",
    "INFMAX = float('inf')\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "\n",
    "def input():\n",
    "    return sys.stdin.readline().rstrip()\n",
    "\n",
    "\n",
    "def end(r=-1):\n",
    "    print(r)\n",
    "    exit()\n",
    "\n",
    "\n",
    "# --idea\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/15 16:23\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str],\n",
    "                                     groups: List[int]) -> List[str]:\n",
    "        def ok(s, t):\n",
    "            return len(s) == len(t) and sum(x != y for x, y in zip(s, t)) == 1\n",
    "\n",
    "        f = [1] * n\n",
    "        pre = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if f[j] >= f[i] and groups[j] != groups[i]:\n",
    "                    f[i] = f[j] + 1\n",
    "                    pre[i] = j\n",
    "\n",
    "        i = f.index(max(f))\n",
    "        ans = []\n",
    "        while i != -1:\n",
    "            ans.append(i)\n",
    "            i = pre[i]\n",
    "        return [words[i] for i in reversed(ans)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        maxr=[]\n",
    "        d=dict()\n",
    "        def f(pos):\n",
    "            if pos in d:return d[pos].copy()\n",
    "            if pos==len(groups)-1:\n",
    "                return [pos]\n",
    "            if groups[pos]!=groups[pos+1]:\n",
    "                maxr=[pos]\n",
    "            else:\n",
    "                return []\n",
    "            maxr2=[]\n",
    "            for p2 in range(pos+1,len(words)):\n",
    "                r=f(p2)\n",
    "                if len(r)>len(maxr2):\n",
    "                    maxr2=r\n",
    "            d[pos]=maxr+maxr2\n",
    "            return d[pos]\n",
    "\n",
    "\n",
    "        for pos in range(len(groups)):\n",
    "            r=f(pos)\n",
    "            if len(r)>len(maxr):\n",
    "                maxr=r\n",
    "        a=[]\n",
    "        for e in maxr:\n",
    "            a.append(words[e])\n",
    "        return a\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
